package algo;

import util.RandomArray;
import java.util.Arrays;

/**
 * Created by pc on 2015/1/19.
 * 首先从左边找出有序列表的最右边需移动的元素下标，标记之*
 * 比较适用于已经部分有序的排序* 
 * 比较次数为 n*(n-1)/4, 交换次数为基本等于比较次数*
 */
public class InsertSort {
    //不太明白的方法
    public static void sort1(int[] toSortArr) {
        int i, j, k;
        for (i = 1; i < toSortArr.length; i++) {
            //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
            for (j = i - 1; j >= 0; j--)
                if (toSortArr[j] < toSortArr[i])
                    break;

            //如找到了一个合适的位置
            System.out.println("i:" + i + ", j: " + j);
            if (j != i - 1) {
                System.out.println("i != j");
                //将比a[i]大的数据向后移
                int temp = toSortArr[i];
                for (k = i - 1; k > j; k--)
                    toSortArr[k + 1] = toSortArr[k];
                //将a[i]放到正确位置上
                toSortArr[k + 1] = temp;
            } else {
                System.out.println("i == j");
            }
        }

    }

    public static void sort(int[] toSortArr) {
        int toMovePos, temp;
        for (int i = 0; i < toSortArr.length - 1; i++) {
            //寻找第一个右边比左边小的元素
            if (toSortArr[i + 1] < toSortArr[i]) {
                //记下这个元素的下标和值
                toMovePos = i + 1;
                temp = toSortArr[toMovePos];
//                System.out.println("need move index: " + toMovePos + ", element: " + temp);
                while (toMovePos > 0) {
                    if (toSortArr[toMovePos - 1] > temp) {
                        //左边的元素比右边的大，需要向右移动
                        toSortArr[toMovePos] = toSortArr[toMovePos - 1];
                    } else {
                        //找到了需要插入的适当位置，结束本次循环
                        toSortArr[toMovePos] = temp;
                        break;
                    }
                    toMovePos--;
                }
                if (toMovePos == 0) {
                    //到了最左边，直接插入，结束
                    toSortArr[0] = temp;
                }
                System.out.println("now array: " + Arrays.toString(toSortArr));
            }
        }
    }

    public static void main(String[] args) {
//        int[] testArr = new int[]{23, 45, 23, 34, 10};
        int[] testArr = RandomArray.getRandomIntArray(10);
        System.out.println("before sort: " + Arrays.toString(testArr));
        InsertSort.sort(testArr);
//        InsertSort.sort1(testArr);
        System.out.println("after sort: " + Arrays.toString(testArr));

    }
}

